/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/rotate-list
   @Language: C++
   @Datetime: 16-02-09 08:27
   */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
	/**
	 * @param head: the list
	 * @param k: rotate to the right k places
	 * @return: the list after rotation
	 */
	ListNode *rotateRight(ListNode *head, int k) {
		// write your code here
		if (head==NULL || head->next==NULL) return head;
		ListNode *p;
		int n = 1;
		for(p=head; p->next; ++n, p=p->next); // list length
		p->next = head;     // relink to head
		for(k=n-k%n; k--; p=head,head=head->next);
		p->next = NULL;     // cut down list
		return head;
	}
};
